/*
 * RobotPlayer.java
 *
 * AI thread for each individual robot in a battlecode team.
 *
 * Copyright 2008 Kevin Liu
 *                Arnie Mengle
 *                Conrad Meyer
 *                Shawn Xu
 */

package team166;

import battlecode.common.*;
import static battlecode.common.GameConstants.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;

public class RobotPlayer implements Runnable
{
  private final RobotController myRC;

  /******************
   *     Cache      *
   ******************/
  private MapLocation currLoc;
  private int currX;
  private int currY;
  private boolean towerInSight = false;
  
  /*
   * variables that don't change
   */
  private final RobotType type;
  private final Team myTeam;
  private final double myMaxEnergonLevel; //TODO: use this rather than calling methods on myRC
  private final boolean iCanAttackAir;
  private final boolean iCanAttackGround;
  private final int myID;
  private final Robot myRobot;  

  private MapLocation[] archonLocations;
  private HashMap<MapLocation, TerrainTile> map = new HashMap<MapLocation, TerrainTile>();
  private LinkedList<Message> outMessageQ = new LinkedList<Message>();
  private HashMap<MapLocation, Integer> towers = new HashMap<MapLocation, Integer>();
  private Queue<MapLocation> towersQ = new LinkedList<MapLocation>();
  private Direction[] directions;
  private double unitspace_archon_ratio = 2.0;

  // constants  
  private static final int SCOUT_UNITSPACE = 1;
  private static final int SOLDIER_UNITSPACE = 2;
  private static final int EVOLVED_UNITSPACE = 4; // all evolved units have equal energon
  // these values based on energon, since upkeep is 1/100 of max energon
  
  private static final TerrainTile.TerrainType LAND = TerrainTile.TerrainType.LAND;
  private static final TerrainTile.TerrainType WATER = TerrainTile.TerrainType.WATER;

  public RobotPlayer(RobotController rc)
  {
    myRC = rc;
    myTeam = myRC.getTeam();
    type = myRC.getRobotType();
    myMaxEnergonLevel = myRC.getMaxEnergonLevel();
    iCanAttackAir = myRC.canAttackAir();
    iCanAttackGround = myRC.canAttackGround();
    myRobot = myRC.getRobot();
    myID = myRobot.getID();
    directions = Direction.values();    
    currLoc = myRC.getLocation();
    currX = currLoc.getX();
    currY = currLoc.getY();
    try {
      fullScan();
    }
    catch (GameActionException e) {}    
  }

  /**
   * Debug Methods
   */

  private void debug_message(String str)
  {
    // we can comment this out to disable debugging
    System.out.println(str);
  }

  private void debug_printPath(MapNode path)
  {
    int num = 0;
    while (path != null)
    {
      debug_message(String.valueOf(num++) + ": Coordinates: " + path.loc.getX() + ", " + path.loc.getY());
      path = path.child;
    }
  }
  
  private void debug_MapLocation(MapLocation loc)
  {
    if (loc == null) debug_message("MapLocation is null.");
    else debug_message("Coordinates == " + loc.getX() + ", " + loc.getY());
  }

  private void debug_MapNode(MapNode n, String mapNodeName)
  {
    if (n == null) debug_message(mapNodeName + " is null.");
    else
    {
      debug_message("");
      debug_message("Printing " + mapNodeName + " information:");
      if (n.loc == null) debug_message(mapNodeName + " Coordinates == null");
      else debug_message(mapNodeName + " Coordinates == " + n.loc.getX() + ", " + n.loc.getY());
      debug_message(mapNodeName + " F == " + n.F);
      debug_message(mapNodeName + " G == " + n.G);
      debug_message(mapNodeName + " H == " + n.H);
      if (n.parent == null || n.parent.loc == null) debug_message(mapNodeName + " parent location == null");
      else debug_message(mapNodeName + " parent location == " + n.parent.loc.getX() + ", " + n.parent.loc.getY());
      debug_message("");
    }
  }

  /*********************
   * Scanning Routines *
   *********************/

  private static final int[] archonOrthScanRight = { -6,-5,-4,-3,-2,-1, 0, 1, 2, 3, 4, 5, 6};
  private static final int[] archonOrthScanForward = {0, 3, 4, 5, 5, 5, 6, 5, 5, 5, 4, 3, 0};
  private static final int[] archonDiagScanRight = { -3,-2, 0, 0, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 5, 5};
  private static final int[] archonDiagScanForward = {5, 5, 6, 5, 5, 5, 5, 4, 4, 3, 3, 2, 1, 0, 0,-2,-3};

  private static final int[] scoutOrthScanRight = { -5,-4,-3,-2,-1, 0, 1, 2, 3, 4, 5};
  private static final int[] scoutOrthScanForward = {0, 3, 4, 4, 4, 5, 4, 4, 4, 3, 0};
  private static final int[] scoutDiagScanRight = { -3,-2, 0, 0, 1, 2, 3, 3, 4, 4, 4, 4, 5, 4, 4};
  private static final int[] scoutDiagScanForward = {4, 4, 5, 4, 4, 4, 4, 3, 3, 2, 1, 0, 0,-2,-3};
  
  private static final int[] bomberOrthScanRight = { -4, -3, -2, -1, 0, 1, 2, 3, 4 };
  private static final int[] bomberOrthScanForward = {0,  2,  3,  3, 4, 3, 3, 2, 0 };
  private static final int[] bomberDiagScanRight = { -2, 0, 0, 1, 2, 2, 3, 3, 3, 4, 3 };
  private static final int[] bomberDiagScanForward = {3, 4, 3, 3, 3, 2, 2, 1, 0, 0, -2};

  private static final int[] soldierOrthScanRight = { -3,-2,-1, 0, 1, 2, 3};
  private static final int[] soldierOrthScanForward = {0, 2, 2, 3, 2, 2, 0};
  private static final int[] soldierDiagScanRight =  {-2, 0, 0, 1, 2, 2, 2, 3};
  private static final int[] soldierDiagScanForward =  {2, 3, 2, 2, 2, 1, 0, 0};

  private static final int[] sniperOrthScanRight = {-2,-1, 0, 1, 2};
  private static final int[] sniperOrthScanForward = {3, 3, 4, 3, 3};
  private static final int[] sniperDiagScanRight = {0, 0, 1, 2, 2, 3, 3, 3, 4};
  private static final int[] sniperDiagScanForward = {4, 3, 3, 3, 2, 2, 1, 0, 0};


  private static final int[] mortarOrthScanRight = sniperOrthScanRight;
  private static final int[] mortarOrthScanForward = {2, 2, 3, 2, 2};
  private static final int[] mortarDiagScanRight = {0, 0, 1, 2, 2, 2, 3};
  private static final int[] mortarDiagScanForward = {3, 2, 2, 2, 1, 0, 0};

  private MapLocation scan() throws GameActionException
  {    
        switch (type)
        {
          case ARCHON:
            if (myRC.getDirection().isDiagonal()) partialScan(archonDiagScanRight, archonDiagScanForward);
            else partialScan(archonOrthScanRight, archonOrthScanForward);
            break;
          case SOLDIER:
            if (myRC.getDirection().isDiagonal()) partialScan(soldierDiagScanRight, soldierDiagScanForward);
            else partialScan(soldierOrthScanRight, soldierOrthScanForward);
            break;
          case SCOUT:
            if (myRC.getDirection().isDiagonal()) partialScan(scoutDiagScanRight, scoutDiagScanForward);
            else partialScan(scoutOrthScanRight, scoutOrthScanForward);
            break;
          case MORTAR:
              if (myRC.getDirection().isDiagonal()) partialScan(mortarDiagScanRight, mortarDiagScanForward);
              else partialScan(mortarOrthScanRight, mortarOrthScanForward);
            break;
          case SNIPER:
              if (myRC.getDirection().isDiagonal()) partialScan(sniperDiagScanRight, sniperDiagScanForward);
              else partialScan(sniperOrthScanRight, sniperOrthScanForward);
            break;
          case BOMBER:
              if (myRC.getDirection().isDiagonal()) partialScan(bomberDiagScanRight, bomberDiagScanForward);
              else partialScan(bomberOrthScanRight, bomberOrthScanForward);
            break;
        }
    for (Robot r : myRC.senseNearbyGroundRobots())
    {           
      RobotInfo ri = myRC.senseRobotInfo(r);
      if (ri.type == RobotType.TOWER && ri.team != myTeam) {
        towerInSight = true;
        if (!towersQ.contains(ri.location)) towersQ.offer(ri.location); 
        return ri.location;      
      }      
    }
    return null;
  }

  private void fullScan() throws GameActionException
  {   
    int radius = type.sensorRadius();
    for (int x = -radius; x <= radius; x++)
    {
      for (int y = -radius; y <= radius; y++)
      {
        MapLocation temp = new MapLocation(currX+x, currY+y);
        TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
        if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
      }
    }    
  }

  private void partialScan(int[] scanRight, int[] scanForward) throws GameActionException
  {
    towerInSight = false;
    MapLocation temp;
    switch (myRC.getDirection())
    {
      case NORTH_EAST:
      case NORTH:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX + scanRight[i], currY - scanForward[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);          
        }
        break;
      case SOUTH_EAST:
      case SOUTH:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX + scanRight[i], currY + scanForward[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
        }
        break;
      case EAST:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX + scanForward[i], currY + scanRight[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
        }
        break;
      case NORTH_WEST:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX - scanRight[i], currY - scanForward[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
        }
        break;
      case WEST:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX - scanForward[i], currY + scanRight[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
        }
        break;
      case SOUTH_WEST:
        for(int i = 0; i < scanRight.length; i++)
        {
          temp = new MapLocation(currX - scanRight[i], currY + scanForward[i]);
          TerrainTile tempTerrainTile = myRC.senseTerrainTile(temp);
          if (tempTerrainTile != null && tempTerrainTile.getType() != LAND) map.put(temp,tempTerrainTile);
        }
        break;
    }
  }

  /***************************
   *   Navigation Routines   *
   ***************************/  
  
  private Direction directionTo(MapLocation loc)
  {
    int locX = loc.getX();  
    int locY = loc.getY();
    if(currX < locX)
    {
      if(currY < locY) return Direction.SOUTH_EAST;
      if(currY > locY) return Direction.NORTH_EAST;
      else return Direction.EAST;
    }
    if(currX > locX)
    {
      if(currY < locY) return Direction.SOUTH_WEST;
      if(currY > locY) return Direction.NORTH_WEST;
      else return Direction.WEST;
    }
    if(currY < locY) return Direction.SOUTH;
    else return Direction.NORTH;
  }  

  /**
   * A* Navigation
   */
  
  // I don't trust the efficiency of math.abs(). Call me paranoid -shawn
  private static int abs(int x) { return x < 0 ? -x:x; }

  private MapNode AstarPathFinder_HashMap(MapLocation end, int lookAheadLimit) throws GameActionException,
          NullPointerException
  {
    HashMap<MapLocation, MapNode> open = new HashMap<MapLocation, MapNode>();
    HashMap<MapLocation, MapNode> closed = new HashMap<MapLocation, MapNode>();
    PriorityQueue<MapNode> openHeap = new PriorityQueue<MapNode>(160);
    int endX = end.getX();
    int endY = end.getY();
    int currIt = 0;
    MapNode currNode = null;
    MapNode startNode = new MapNode(currLoc, null, 0,10*(abs(endX-currX)+abs(endY-currY)));
    open.put(currLoc, startNode);
    openHeap.offer(startNode);
    for (Direction d : directions)
    {
      if (d == Direction.NONE || d == Direction.OMNI) break;
      MapLocation adj = currLoc.add(d);
      if (myRC.canSenseSquare(adj) && myRC.senseGroundRobotAtLocation(adj) != null) closed.put(adj, new MapNode());     
    }
    while (true)
    {
      MapNode tempEnd = closed.get(end);
      if (tempEnd != null) return (tempEnd.loc == null)? null:tempEnd;      
      if (open.isEmpty()) return null;
      currNode = openHeap.poll();
      open.remove(currNode.loc);
      closed.put(currNode.loc, currNode);
      if (++currIt > lookAheadLimit) return currNode;
      for (Direction d : directions)
      {
        if (d == Direction.NONE || d == Direction.OMNI) break;
        MapLocation temp = currNode.loc.add(d);
        if (closed.get(temp) != null) continue;
        int gVal = (d.isDiagonal())? 14:10;
        MapNode m = open.get(temp);
        if (m != null)
        {
          int newG = currNode.G + gVal;
          if (newG < m.G)
          {
            m.parent = currNode;
            m.setG(newG);
            openHeap.remove(m);
            openHeap.offer(m);
          }
          continue;
        }
        if (map.get(temp) != null)
        {
          closed.put(temp, new MapNode());
          continue;
        }
        else
        {
          MapNode candidate = new MapNode(temp, currNode, gVal+currNode.G,10*(abs(endX-temp.getX())+abs(endY-temp.getY())));
          open.put(temp, candidate);
          openHeap.offer(candidate);          
        }
      }
    }
  }

  private enum PathingStatus {
    NO_PATH, SUCCESS, REACHED_DEST, SURROUNDED
  }

  private PathingStatus calculatePath(MapLocation dest, int cutoff) throws GameActionException
  {
    if (currLoc.equals(dest)) return PathingStatus.REACHED_DEST;
    //TerrainTile t;
    //if ((t = map.get(dest)) != null) return PathingStatus.NO_PATH;                      
    // Now test to see if we're surrounded
    int numAdjRobots = 0;
    for (Direction d : directions)
    {
      if (d == Direction.NONE || d == Direction.OMNI) break;
      MapLocation temp = currLoc.add(d);      
      if (myRC.canSenseSquare(temp) && myRC.senseGroundRobotAtLocation(temp) != null) numAdjRobots++;      
    }
    if (numAdjRobots >= 8) return PathingStatus.SURROUNDED;
    try
    {
    if ((astarStat.currentPath = AstarPathFinder_HashMap(dest, cutoff)) == null) return PathingStatus.NO_PATH;
    }
    catch (NullPointerException x) { return PathingStatus.NO_PATH; }
    catch (GameActionException gae) { return PathingStatus.NO_PATH; }
    boolean hasIntermediate = (astarStat.currentPath.parent == null)? false:true;
    while (astarStat.currentPath.parent != null)
    {
      astarStat.currentPath.parent.child = astarStat.currentPath;
      astarStat.currentPath = astarStat.currentPath.parent;
    }
    if (hasIntermediate) astarStat.currentPath = astarStat.currentPath.child;
    return PathingStatus.SUCCESS;
  }

  private AstarStatus astarStat = new AstarStatus();
  
  public class AstarStatus {
    public MapLocation currentDest = null;    
    public MapNode currentPath = null;
    public boolean initialArchonFind = false; 
    public int nearestIndex = 0;
    public MapLocation nearestBase = null;      
    
    private void resetBase() {
      this.currentPath = null;
      this.currentDest = null;
      this.nearestBase = null;
  }
    
    private void resetTower() {
      this.currentDest = null;
      this.currentPath = null;
    }       
  }
  
  private enum TowerPathStatus {
    FAILED, REACHED, IN_PROGRESS
  }   

  private TowerPathStatus followArchon() throws GameActionException {
    MapLocation nearestArchon;   
    if (!astarStat.initialArchonFind) {
      astarStat.initialArchonFind = true; 
      MapLocation[] archonLoc = myRC.senseAlliedArchons(); 
      if (archonLoc == null || archonLoc.length == 0) return TowerPathStatus.FAILED;       
      int closestDist = 1000000;
      for (int i = 0; i < archonLoc.length; i++) {
        if (archonLoc[i].equals(currLoc)) continue;
        int dist = currLoc.distanceSquaredTo(archonLoc[i]); 
        if (dist < closestDist) {
            closestDist = dist; 
            astarStat.nearestIndex = i;
        }         
      }      
    }     
    nearestArchon = myRC.senseAlliedArchons()[astarStat.nearestIndex]; // beware, if the archon was killed, there could be a null pointer    
    if (currLoc.isAdjacentTo(nearestArchon)) return TowerPathStatus.REACHED;     
    move(directionTo(nearestArchon));
    return TowerPathStatus.IN_PROGRESS; 
  } 
  
  private TowerPathStatus moveToTower_soldier() throws GameActionException {
    if (towerInSight) return swarm(towersQ.peek());
    return (bugStat.traceStatus == TraceStatus.TracedBoth)? AstarToTower():bugMove(myRC.senseClosestUnknownTower());
  }
  
  private TowerPathStatus moveToTower_archon() throws GameActionException {
    if (towerInSight) return TowerPathStatus.REACHED;
    return (bugStat.traceStatus == TraceStatus.TracedBoth)? AstarToTower():bugMove(myRC.senseClosestUnknownTower());
  }
  
  private TowerPathStatus moveToBase() throws GameActionException {
    if (astarStat.nearestBase != null && myRC.canSenseSquare(astarStat.nearestBase)) return swarm(astarStat.nearestBase);
    return AstarToBase();
  }
  
  // 1: reached tower
  // 2: in progress
  private TowerPathStatus AstarToTower() throws GameActionException
  {      
    if (astarStat.currentPath == null)
    {
      astarStat.currentDest = calculateMythicalLocation(myRC.senseClosestUnknownTower());
      switch(calculatePath(astarStat.currentDest, 30))
      {
        case SURROUNDED:
          myRC.yield();
          return TowerPathStatus.IN_PROGRESS;    
        case REACHED_DEST:  
        case NO_PATH:          
          astarStat.resetTower();
          return TowerPathStatus.REACHED;                                                 
      }
    }
    astarStat.currentPath = (move(directionTo(astarStat.currentPath.loc))) ? astarStat.currentPath.child : null;
    return TowerPathStatus.IN_PROGRESS;
  }
  
  private TowerPathStatus AstarToKnownTower(MapLocation currentDest) throws GameActionException
  {      
    if (astarStat.currentPath == null)
    {
      switch(calculatePath(currentDest, 30))
      {
        case SURROUNDED:
          myRC.yield();
          return TowerPathStatus.IN_PROGRESS;    
        case REACHED_DEST:  
        case NO_PATH:          
          astarStat.resetTower();
          return TowerPathStatus.REACHED;                                                 
      }
    }
    astarStat.currentPath = (move(directionTo(astarStat.currentPath.loc))) ? astarStat.currentPath.child : null;
    return TowerPathStatus.IN_PROGRESS;
  }
  
  private TowerPathStatus AstarToBase() throws GameActionException {
      if (astarStat.nearestBase == null) {
          MapLocation[] towerLoc = myRC.senseAlliedTowers();
          if (towerLoc == null || towerLoc.length == 0) myRC.suicide(); // If we have no more towers left...SAMURAI HONOR!!!
          MapLocation closest = towerLoc[0];
          int closestDist = currLoc.distanceSquaredTo(closest);
          for (MapLocation tower : towerLoc) {
            int dist = currLoc.distanceSquaredTo(tower);
            if (dist < closestDist) {
                closest = tower;
                closestDist = dist;
            }
          }
          astarStat.nearestBase = closest;
          astarStat.currentDest = closest;
      }
      if (astarStat.currentPath == null)
      {                  
        switch(calculatePath(astarStat.currentDest, 30))
        {
          case SURROUNDED:
            myRC.yield();
            return TowerPathStatus.IN_PROGRESS;                           
          case NO_PATH:                                     
          case REACHED_DEST:
            astarStat.resetBase();
            return TowerPathStatus.REACHED;                        
          }
      }
      astarStat.currentPath = (move(directionTo(astarStat.currentPath.loc))) ? astarStat.currentPath.child : null;
      return TowerPathStatus.IN_PROGRESS;     
  }  
  
  private static final int[][] swarm_x = { {-1, -1, -1,  0, 0,  1, 1, 1}, {-2, -2, -2, -2, -2, -1, -1,  0, 0,  1, 1,  2,  2, 2, 2, 2} };
  private static final int[][] swarm_y = { {-1,  0,  1, -1, 1, -1, 0, 1}, {-2, -1,  0,  2,  1, -2,  2, -2, 2, -2, 2, -1, -1, 0, 1, 2} };  
  
  private MapLocation findVacancy(MapLocation dest) throws GameActionException {
      int destX = dest.getX();
      int destY = dest.getY();
      for (int layer = 0; layer < 2; layer++) {          
          int length = swarm_x[layer].length;          
          for (int i = 0; i < length; i++) {              
              MapLocation temp = new MapLocation(destX + swarm_x[layer][i], destY + swarm_y[layer][i]);
              if (temp.equals(currLoc)) return null;
              if (myRC.canSenseSquare(temp)) {
                  if (map.get(temp) == null && myRC.senseGroundRobotAtLocation(temp) == null) return temp;                                                                                          
              } else return temp;                                
          }
      }
      return null;
  }
  
  private TowerPathStatus swarm(MapLocation focus) throws GameActionException{
      if ((astarStat.currentDest = findVacancy(focus)) == null) {
          astarStat.currentPath = null;
          astarStat.currentDest = null;
          return TowerPathStatus.REACHED;
      }
      if (astarStat.currentPath == null) {
        switch(calculatePath(astarStat.currentDest, 20)) {
          case SURROUNDED: 
            myRC.yield();
            return TowerPathStatus.IN_PROGRESS;
        }
      }
      astarStat.currentPath = (move(directionTo(astarStat.currentPath.loc))) ? astarStat.currentPath.child : null;
      return TowerPathStatus.IN_PROGRESS; 
  }

  private MapLocation calculateMythicalLocation(Direction dir)
  {
    switch (dir)
    {
      case NORTH: return new MapLocation(currX, currY - 7);
      case SOUTH: return new MapLocation(currX, currY + 7);
      case EAST: return new MapLocation(currX + 7, currY);
      case WEST: return new MapLocation(currX - 7, currY);
      case NORTH_EAST: return new MapLocation(currX + 6, currY - 6);
      case NORTH_WEST: return new MapLocation(currX - 6, currY - 6);
      case SOUTH_EAST: return new MapLocation(currX + 6, currY + 6);
      case SOUTH_WEST: return new MapLocation(currX - 6, currY + 6);
    }
    return null;
  }

  private boolean move(Direction adjDir) throws GameActionException
  {        
    if (adjDir == Direction.NONE) return false;            
    while (myRC.isMovementActive()) myRC.yield();    
    if (myRC.getDirection() != adjDir)
    {        
      myRC.setDirection(adjDir);
      myRC.yield();
    }
    if (myRC.canMove(adjDir))
    {                     
      myRC.moveForward();
      myRC.yield();
      currLoc = myRC.getLocation();
      currX = currLoc.getX();
      currY = currLoc.getY();            
      MapLocation mloc = scan();
      if (mloc != null) sendTowerLocation(mloc);
      return true;
    }
    return false;        
  }
  
  enum TraceStatus {
    Neither, TracedLeft, TracedRight, TracedBoth
  }
  
  class BugNode {
    Direction d;
    MapLocation mloc;
    BugNode parent;
    BugNode child;
      
    public BugNode(Direction _d, MapLocation _mloc, BugNode p) {
      d = _d;
      mloc = _mloc;
      parent = p;
    }
  }
  
  public class BugStatus {                     
    TraceStatus traceStatus = TraceStatus.TracedLeft;    
    boolean tracing = false;
    boolean returning = false;
    int maxTraceDist = 16;
    int currTraceDist = 0;
    int waitingPeriod = 0;
    BugNode fork = null; 
  }
  
  private BugStatus bugStat = new BugStatus();
  
  private TowerPathStatus bugMove(Direction targetDir) throws GameActionException {
    if (bugStat.tracing) {      
      if (bugStat.traceStatus == TraceStatus.TracedBoth) return TowerPathStatus.FAILED;
      Direction d = myRC.getDirection();
      int i = 0;
      while (myRC.canMove(d)) {
        if (i++ == 8) break;
        if (d == targetDir) {
          bugStat.tracing = false;
          return TowerPathStatus.IN_PROGRESS;
        }
        d = (bugStat.traceStatus == TraceStatus.TracedLeft) ? d.rotateLeft(): d.rotateRight();
      }   
      i = 0;
      while (!myRC.canMove(d)) {
        if (i++ == 8) {
          myRC.yield();
          return TowerPathStatus.IN_PROGRESS;
        }            
        d = (bugStat.traceStatus == TraceStatus.TracedLeft) ? d.rotateRight(): d.rotateLeft();
      }
      BugNode temp = bugStat.fork;
      while (temp != null) {
        if (temp.mloc.equals(currLoc.add(d))) {
          bugStat.traceStatus = (bugStat.traceStatus == TraceStatus.TracedLeft) ? TraceStatus.TracedRight:TraceStatus.TracedBoth;
          bugStat.tracing = false;
          bugStat.returning = true;
          bugStat.currTraceDist = 0;
          return TowerPathStatus.IN_PROGRESS;
        }
        temp = temp.parent;
      }
      if (bugStat.fork == null) bugStat.fork = new BugNode(d, currLoc, null);
      else bugStat.fork = bugStat.fork.child = new BugNode(d, currLoc, bugStat.fork);          
      move(d);      
      if (++bugStat.currTraceDist >= bugStat.maxTraceDist) {
        bugStat.traceStatus = (bugStat.traceStatus == TraceStatus.TracedLeft) ? TraceStatus.TracedRight:TraceStatus.TracedBoth;              
        bugStat.currTraceDist = 0;
      }        
    } else if (bugStat.returning) {
      if (bugStat.fork == null) {
        bugStat.returning = false;
        bugStat.tracing = true;
      } else {
        move(bugStat.fork.d.opposite());
        bugStat.fork = bugStat.fork.parent;
      }
    } else if (!move(targetDir)) {      
      if (map.get(currLoc.add(targetDir)) != null) bugStat.tracing = true;    
      else if (bugStat.waitingPeriod++ >= 3) {
        bugStat.tracing = true;
        bugStat.waitingPeriod = 0;
      }
      else myRC.yield();      
    }
    return TowerPathStatus.IN_PROGRESS;
  }

  /**********************
   * Attacking Routines *
   **********************/

  private void attackRoutines() throws GameActionException
  {    
    if (iCanAttackGround && !myRC.isAttackActive() && !myRC.isMovementActive())
    {
      Robot[] nearbyGroundRobots = myRC.senseNearbyGroundRobots();
      for (Robot currentRobot : nearbyGroundRobots)
      {
        RobotInfo ri = myRC.senseRobotInfo(currentRobot);
        if (ri.team != myTeam && myRC.canAttackSquare(ri.location))
        {
          myRC.attackGround(ri.location);
          continueCombat();
          return;
        }
      }
    }
    if (iCanAttackAir && !myRC.isAttackActive() && !myRC.isMovementActive())
    {
      Robot[] nearbyAirRobots = myRC.senseNearbyAirRobots();
      for (Robot currentRobot : nearbyAirRobots)
      {
        RobotInfo ri = myRC.senseRobotInfo(currentRobot);
        if (ri.team != myTeam && myRC.canAttackSquare(ri.location))
        {
          myRC.attackAir(ri.location);
          continueCombat();
          return;
        }
      }
    }    
  }
  
  /**
   * the purpose of this method is to keep our robots in fight mode when they see an enemy. once attackroutines is called,
   * there will be a recursive loop between these two functions while there is still an enemy. once there isn't, reach the 
   * return statements, thereby avoiding wasted bytecode
   *
   * i predict that once a robot sees an enemy, they will stop what they're doing and shoot until they can't shoot anymore.
   * maybe i'll work in something later so it can move in between attacks
   *
   * TODO: do the above
   *
   * @author kevin
   */
  private void continueCombat() throws GameActionException
  {
      myRC.yield();
      
      attackRoutines();
  }

  /********************
   * General Routines *
   ********************/

  public void run()
  {    
    while (true)
    {
      try
      {
        basicRoutines();
        switch (type)
        {
          case ARCHON:
            //archonRoutinesObsolete();
            //archonRoutinesTesting1();
            //archonRoutinesTesting2();
            archonRoutines();
            break;
          case SOLDIER:
            soldierRoutines();
            break;
          case SCOUT:
            scoutRoutines();
            break;
          case MORTAR:
            mortarRoutines();
            break;
          case SNIPER:
            sniperRoutines();
            break;
          case BOMBER:
            bomberRoutines();
            break;
        }
      }
      catch(Exception e)
      {
        e.printStackTrace();
      }
    }
  }

  // this method is always called at the beginning of the turn
  private void basicRoutines()
  {     
    // for debugging purposes
    if (Clock.getRoundNum() % 250 == 15)
    {
      //debug_message("\tMap:\t" + map.size());
      //debug_message("\thasOrigin:\t" + (origin != null));
    }

    if (originCoolDown > 0) originCoolDown--;

    // TODO: make finding the origin a priority if they don't
    // yet have it. sorta. -konrad

    processMessages();
    archonLocations = myRC.senseAlliedArchons();

    // TODO: implement this in the future -konrad
  }
   
  /*
   * are we bothering to do anything with this? -kevin
   */
  private void nonArchonRoutines()
  {
      
  }

  /***************************
   * Robot Specific Routines *
   ***************************/

  private State state; 
  
  private enum State {
    ARCHON_INITIAL, ARCHON_BUILDING_ARMY, ARCHON_LOW_ENERGON,
    ARCHON_FINDING_TOWER, ARCHON_ENGAGING_TOWER, ARCHON_ENGAGING_ENEMY,
    ARCHON_RETREATING_TO_BASE, ARCHON_IDLE
  }

  /******************************
   * for archons to keep track of
   ******************************/
  private int soldierCount = 0;
  private int scoutCount   = 0;
  private int bomberCount  = 0;
  private int archonCount  = 8;
  private int mortarCount  = 0;
  private int sniperCount  = 0;

  //minimum energon needed before spawning a new unit
  private static final double MIN_SPAWN_ENERGON = 40.0;
  //retreat if energon falls below this
  private static final double CRITICAL_ENERGON_RETREAT = 10.0;  

  /**
   * Archon Routines
   */
  
  /*
   * the problem with this method is that is considers all the units on our team. if we are at the army size limit
   * as determined by this method, a lone archon with no army around it will think it has an army - but the army is 
   * not with it. thus, what we need to do is have archons lump together by following a leader OR having some way
   * of deciding, and agreeing on, which tower to go for next. 
   * -kevin
   */
  private boolean needToBuildArmy() throws GameActionException
  {
    /*int totalUnitSpace = scoutCount + SOLDIER_UNITSPACE * soldierCount + EVOLVED_UNITSPACE *
      (sniperCount + mortarCount + bomberCount);
    return (totalUnitSpace < UNITSPACE_ARCHON_RATIO * archonCount);*/
      int fighters = 0;
      int archons = 0;
      Robot[] grounds = myRC.senseNearbyGroundRobots();
      for (Robot r : grounds)
      {
          RobotInfo ri = myRC.senseRobotInfo(r);
          if (ri.team == myTeam)
          {
              if (ri.type == RobotType.ARCHON) archons++;
              else fighters++;
          }
      }
      Robot[] airs = myRC.senseNearbyAirRobots();
      for (Robot r : airs)
      {
          RobotInfo ri = myRC.senseRobotInfo(r);
          if (ri.team == myTeam)
          {
              fighters++;
          }
      }
      return (fighters < archons * unitspace_archon_ratio); //for now build army if local ratio of units is less than 2 units per archon
  }

  private boolean gameStart = true;
//  private int callsToMethod = 0; /*temporary variable to see what the hell the archons have as their set state after
//   the first few hundred rounds */
  private void archonRoutines() throws GameActionException
  {
    while (gameStart == true && myRC.getEnergonLevel() < 20.0)
    {
        switch(AstarToTower())
        {
            case IN_PROGRESS:
                break;
        }
    }
    gameStart = false;
    soldierCount = myRC.getUnitCount(RobotType.SOLDIER);
    scoutCount   = myRC.getUnitCount(RobotType.SCOUT);
    bomberCount  = myRC.getUnitCount(RobotType.BOMBER);
    archonCount  = myRC.getUnitCount(RobotType.ARCHON);
    mortarCount  = myRC.getUnitCount(RobotType.MORTAR);
    sniperCount  = myRC.getUnitCount(RobotType.SNIPER);
    
    if (needToBuildArmy() && state != State.ARCHON_LOW_ENERGON && state != State.ARCHON_RETREATING_TO_BASE) state = State.ARCHON_BUILDING_ARMY;
    else state = State.ARCHON_FINDING_TOWER;
    if (myRC.getEnergonLevel() < CRITICAL_ENERGON_RETREAT)
    {
      state = State.ARCHON_LOW_ENERGON;
    }
    archonDistributeEnergon();
    switch (state)
    {
      case ARCHON_INITIAL: break; //pointless because it'll never be in this state. remove? -kevin
      case ARCHON_BUILDING_ARMY:
        // debug_message("Building Army");
        // we only spawn if we're inside spawn radius AND outside tower attack range
        // otherwise retreat to nearest base
        if (myRC.canSpawn()) reproduce();                       
        else 
          state = State.ARCHON_RETREATING_TO_BASE;
        break;
      case ARCHON_LOW_ENERGON:
        switch (AstarToBase())
        {
          case FAILED:
            state = State.ARCHON_FINDING_TOWER;
            break;
        }
        break;
      case ARCHON_FINDING_TOWER:
        // debug_message("Finding Tower");
        if (nextDest == null) {
            switch (AstarToTower())
            {
                case FAILED:
                state = State.ARCHON_RETREATING_TO_BASE;
                break;
                case REACHED:
                //unitspace_archon_ratio = 3.0;
                state = State.ARCHON_RETREATING_TO_BASE;
                break;
            }
        }
        else
            switch (AstarToKnownTower(nextDest))
            {
                case FAILED:
                state = State.ARCHON_RETREATING_TO_BASE;
                break;
                case REACHED:
                //unitspace_archon_ratio = 3.0;
                nextDest = null;
                state = State.ARCHON_RETREATING_TO_BASE;
                break;
            }
        break;
      case ARCHON_ENGAGING_TOWER:
        // debug_message("Engaging Tower");
        archonDistributeEnergon(); //we need to move around too during combat - place ourselves farther from enemy
        break;
      case ARCHON_RETREATING_TO_BASE:
        // debug_message("Retreating To Base");
        // We want to make sure to first get very close to allied tower, then, once there, check to see if within
        // any enemy tower range, and if so, move farther away from that tower
        switch (AstarToBase())
        {
          case REACHED:
            state = State.ARCHON_BUILDING_ARMY;
            break;
          case FAILED:
            state = State.ARCHON_FINDING_TOWER;
            break;
        }
        break;
      case ARCHON_IDLE:
        // debug_message("Idle");
        archonDistributeEnergon();
        break;
    }
    //following if block is for debugging purposes
//    if (++callsToMethod % 2 == 0 ) //139 is prime
//    {
//        myRC.setIndicatorString(0, state.toString());
//        myRC.breakpoint();
//        if (myRC.getControlBits() == 1)
//        {
//            state = State.ARCHON_BUILDING_ARMY; 
//        }
//        else if (myRC.getControlBits() == 2)
//        {
//            state = State.ARCHON_FINDING_TOWER;
//        }
//    }
    
  }    
  
  private void archonRoutinesTesting1() throws GameActionException
  {           
    bugMove(myRC.senseClosestUnknownTower());    
  }

  private void archonRoutinesTesting2() throws GameActionException
  {        
    switch (moveToTower_soldier())
    {
      case FAILED:
        while (true) myRC.yield();
      case REACHED:        
        while(true) myRC.yield();
    }
  }

  // this method raises TONS of exceptions
  private void archonRoutinesObsolete()
  {
    //moved these here since only archons need to know our unit counts -kevin
    soldierCount = myRC.getUnitCount(RobotType.SOLDIER);
    scoutCount   = myRC.getUnitCount(RobotType.SCOUT);
    bomberCount  = myRC.getUnitCount(RobotType.BOMBER);
    archonCount  = myRC.getUnitCount(RobotType.ARCHON);
    mortarCount  = myRC.getUnitCount(RobotType.MORTAR);
    sniperCount  = myRC.getUnitCount(RobotType.SNIPER);

    if (!sentBallot)
    {
      sendElection();
      sentBallot = true;
    }

    try
    {
      archonDistributeEnergon();

      MapLocation inFront = currLoc.add(myRC.getDirection());
      if (myRC.canSpawn() && myRC.senseGroundRobotAtLocation(inFront) == null
          && myRC.senseTerrainTile(inFront).getType() != TerrainTile.TerrainType.WATER
          && !myRC.hasActionSet() && !myRC.isMovementActive())  //spawning code
      {
        if (myRC.getEnergonLevel() >= 30 && needToBuildArmy())
        {
          myRC.spawn(RobotType.SOLDIER);
          soldierCount = myRC.getUnitCount(RobotType.SOLDIER);
          myRC.yield();
          return;
        }
        //else if (myRC.getEnergonLevel() >= 30 && needToBuildArmy())
        //{
        //  myRC.spawn(RobotType.SCOUT);
        //  scoutCount = myRC.getUnitCount(RobotType.SCOUT);
        //  myRC.yield();
        //  return;
        //}
        // we're going to replace this all by buildArmy() anyway, so no need to have this code.
      }

      //movement: if within tower range
      if (myRC.canSpawn() && !myRC.hasActionSet())
      {
        if (myRC.canMove(myRC.getDirection()) && !myRC.isMovementActive()) //then move forward
        {
          myRC.moveForward();
          myRC.yield();
          currLoc = myRC.getLocation();
          currX = currLoc.getX();
          currY = currLoc.getY();
          return;
        }
        else // otherwise move towards enemy towers
        {
          myRC.setDirection(myRC.senseClosestUnknownTower());
          myRC.yield();
          return;
        }
      }
      //but if out of spawn range, move back within spawn range
      else if (!myRC.canSpawn() && !myRC.hasActionSet() && !myRC.isMovementActive())
      { //this bit of code written by kevin. it makes archons move to the closest allied tower if they are out of range of a tower
        MapLocation[] alliedTowers = myRC.senseAlliedTowers();
        MapLocation closestTower = null;
        int distance = Integer.MAX_VALUE; //huge number so that any distanceSquaredTo() will return a smaller number
        if (alliedTowers.length >= 1)
        {
          closestTower = alliedTowers[0];
          distance = currLoc.distanceSquaredTo(alliedTowers[0]);
        }
        for (int a = 0; a < alliedTowers.length; a++)
        {
          int thisDistance = currLoc.distanceSquaredTo(alliedTowers[a]);
          if (thisDistance < distance)
          {
            closestTower = alliedTowers[a];
            distance = thisDistance;
          }
        }

        //following blocks of code solve for the direction of the closest allied tower -kevin
        if (closestTower != null)
        {
          double dirRadians = Math.atan2((closestTower.getY() - currY), (closestTower.getX() - currX) );
          double dirDegrees = dirRadians * 180 / Math.PI;
          Direction dirToClosestTower = Direction.NORTH; //default - will get changed depending on following code

          if (dirDegrees <= 157.5 && dirDegrees >= 112.5)
          {
            dirToClosestTower = Direction.NORTH_WEST;
          }
          else if (dirDegrees <= 112.5 && dirDegrees >= 67.5)
          {
            dirToClosestTower = Direction.NORTH;
          }
          else if (dirDegrees <= 67.5 && dirDegrees >= 22.5)
          {
            dirToClosestTower = Direction.NORTH_EAST;
          }
          else if (dirDegrees <= 22.5 && dirDegrees >= -22.5)
          {
            dirToClosestTower = Direction.EAST;
          }
          else if (dirDegrees <= -22.5 && dirDegrees >= -67.5)
          {
            dirToClosestTower = Direction.SOUTH_EAST;
          }
          else if (dirDegrees <= -67.5 && dirDegrees >= -112.5)
          {
            dirToClosestTower = Direction.SOUTH;
          }
          else if (dirDegrees <= -112.5 && dirDegrees >= -157.5)
          {
            dirToClosestTower = Direction.SOUTH_WEST;
          }
          else if (dirDegrees <= -157.5 || dirDegrees >= 157.5)
          {
            dirToClosestTower = Direction.WEST;
          }

          if (myRC.canMove(dirToClosestTower) && !myRC.hasActionSet() && !myRC.isMovementActive())
          {
            myRC.setDirection(dirToClosestTower);
            myRC.moveForward();
            currLoc = myRC.getLocation();
            currX = currLoc.getX();
            currY = currLoc.getY();
            myRC.yield();
          }
          else if (!myRC.canMove(dirToClosestTower) && !myRC.hasActionSet() && !myRC.isMovementActive())
          {
            myRC.setDirection(dirToClosestTower.rotateRight());
            myRC.yield();
          }
        }

      }
    }
    catch (GameActionException ex)
    {
      ex.printStackTrace();
    }
  }

  /*
   * we should transfer energon to archons too. i'll implement that sometime... sometime.
   * point is that one archon might have a lot while the other is close to dying. we should have the archon
   * save the other.
   */
  private void archonDistributeEnergon() throws GameActionException
  {
      
    Robot temp;
    double myEnergon = myRC.getEnergonLevel();

    for (Direction d : directions)
    {
      if (d == Direction.NONE || d == Direction.OMNI) break;
      
      MapLocation loc = currLoc.add(d);

      // transfer energon to ground units
      if ((temp = myRC.senseGroundRobotAtLocation(loc)) != null)
      {               
        if ((temp = myRC.senseGroundRobotAtLocation(currLoc.add(d))) != null)
        {
          RobotInfo info = myRC.senseRobotInfo(temp);
          // This only fills it if it can be filled fully. How about partial fills? -konrad
          if (info.type != RobotType.ARCHON && info.eventualEnergon < info.maxEnergon -5
              && myRC.getEnergonLevel() > info.maxEnergon - info.eventualEnergon + 10 && info.team == myTeam)
            //+10 to ensure archon will keep enough for itself to avoid death
            //info.team == myRC.getTeam() in case our archons could transfer energon to adjacent enemies. never been in this
            //situation before, so never witnessed it, but i think it's possible that happens -kevin
          {
              myRC.transferEnergon(info.maxEnergon - info.eventualEnergon, currLoc.add(d), temp.getRobotLevel());
              return;
          }
        }
      //to transfer energon to our air units - previously missing this ability -kevin
      //still TODO: add ability to transfer energon to air unit directly on top of archon
        if ((temp = myRC.senseAirRobotAtLocation(currLoc.add(d))) != null)
        {
          RobotInfo info = myRC.senseRobotInfo(temp);
          if (info.type != RobotType.ARCHON && info.eventualEnergon < info.maxEnergon
              && myRC.getEnergonLevel() > info.maxEnergon - info.eventualEnergon + 10 && info.team == myTeam)
          {
            myRC.transferEnergon(info.maxEnergon - info.eventualEnergon, currLoc.add(d), temp.getRobotLevel());
            return;
          }
        }               
      }
    } 
  }    
  
  private void fillUp(Robot robot, MapLocation loc, double myEnergon, RobotLevel airGround) throws GameActionException
  {
      if (myEnergon <= CRITICAL_ENERGON_RETREAT) return;
      RobotInfo info = myRC.senseRobotInfo(robot);
      if (info.team != myTeam) return;
      double share = info.maxEnergon - info.energonLevel;      
      share = (myEnergon - share < CRITICAL_ENERGON_RETREAT)? myEnergon - CRITICAL_ENERGON_RETREAT : share;
      myRC.transferEnergon(share, loc, airGround);      
  }

  private void shareTo(Robot robot, MapLocation loc, double myEnergon,
      RobotLevel airGround) throws GameActionException
  {
    // these constants can always be tuned
    RobotInfo info;
    if (myRC.canSenseObject(robot)) info = myRC.senseRobotInfo(robot);    
    else return;    
        
    //double dif = info.maxEnergon - info.eventualEnergon;
    final double MAX_SHARE = 10.;
    final double MIN_SHARE = 1.;
    final double GOAL_ENERG = 20.;

    double dif = GOAL_ENERG - info.energonLevel;
    double share = (dif > MAX_SHARE)? MAX_SHARE : dif;
    share = (share < MIN_SHARE)? MIN_SHARE : share;
    share = (share > myEnergon - 20)? (myEnergon - 20) : share;

    if (share > MIN_SHARE && info.team == myTeam)
    {
      myRC.transferEnergon(share, loc, airGround);
    }
  }


  /**
   * Soldier Routines
   */

  private void soldierRoutines() throws GameActionException
  {
    if (myRC.hasActionSet())
    {
        myRC.yield();
    }
    nonArchonRoutines();
    attackRoutines();
    followArchon();
  }
  
  // Only here to make debugging easier. Replace this into the above routines to save bytecode.
  private boolean evolveToSniper()
  {
    if (myRC.getEnergonLevel() >= 6 && myRC.getEventualEnergonLevel() >= 10 && !myRC.isAttackActive() && !myRC.isMovementActive())
    {
      try
      {
        myRC.evolve(RobotType.SNIPER);
        return true;
      }
      catch (GameActionException ex)
      {
        ex.printStackTrace();
      }
    }
    return false;
  }
  
  private boolean evolveToMortar()
  {
    if (myRC.getEnergonLevel() >= 6 && myRC.getEventualEnergonLevel() >= 10 && !myRC.isAttackActive() && !myRC.isMovementActive())
    {
      try
      {
        myRC.evolve(RobotType.MORTAR);
        return true;
      }
      catch (GameActionException ex)
      {
        ex.printStackTrace();
      }
    }
    return false;
  }

  /**
   * Mortar Routines
   */

  private void mortarRoutines() throws GameActionException
  {
    nonArchonRoutines();
    attackRoutines();
  }

  /**
   * Scout Routines
   */

  private void scoutRoutines() throws GameActionException
  {
    if (myRC.hasActionSet())
    {
        myRC.yield();
    }
    nonArchonRoutines();
    attackRoutines();

    //for now, evolve ASAP
    if (evolveToBomber())
    {
    }
    else
    {
      if (myRC.isMovementActive() || !myRC.isAttackActive())
        myRC.yield();
    }
  }
  
  // Only here to make debugging easier. Replace this into the above routine to save bytecode.
  private boolean evolveToBomber()
  {
    if (myRC.getEnergonLevel() >= 6 && myRC.getEventualEnergonLevel() >= 10 && !myRC.isAttackActive() && !myRC.isMovementActive())
    {
      try
      {
        myRC.evolve(RobotType.BOMBER);
        return true;
      }
      catch (GameActionException ex)
      {
        ex.printStackTrace();
      }
    }
    return false;
  }

  /**
   * Bomber Routines
   */

  private void bomberRoutines() throws GameActionException
  {
    nonArchonRoutines();
    attackRoutines();
    AstarToTower();
  }

  /**
   * Sniper Routines
   */

  private void sniperRoutines() throws GameActionException
  {
    nonArchonRoutines();
    attackRoutines();
    followArchon();
  }

  /***********************
   * Networking Routines *
   ***********************/

  // for archon elections
  private MapLocation origin;
  private MapLocation voterMandate;
  private int incumbentID = Integer.MAX_VALUE;
  private boolean sentBallot = false;
  private int originCoolDown = 0;

  // for non archons
  private boolean askedForData = false;

  //store enemy messages so we can guess/know how they organize their info so we can better emulate it
  private ArrayList<Message> interceptedEnemyMessages = new ArrayList<Message>();

  private void safeBroadcast(Message m)
  {
    try
    {
      myRC.broadcast(m);
    }
    catch (GameActionException ex)
    {
      if (ex.getMessage().equals("You cannot queue two messages to broadcast in the same round."))
        outMessageQ.offer(m);
      else ex.printStackTrace();
    }
  }

  private void ourBroadcast(Message m)
  {
    Message n = createMessage(m);
    safeBroadcast(n);
  }

  /**
   * sends out a message with nulls
   */
  private void nullMessageAttack()
  {
    Message m = new Message();
    safeBroadcast(m);
  }

  private MapLocation[] scrambleLocations(MapLocation[] orig)
  {
    // TODO: implement me :)

    return orig;
  }

  private MapLocation[] deScrambleLocations(MapLocation[] scrambled)
  {
    // TODO: implement me :)

    return scrambled;
  }

  private int checkSum(Message m)
  {
    // calculate checksum
    int chksum = 0xBADBEEF; // magic number
    if (m.locations != null) for(MapLocation loc : m.locations) chksum ^= loc.hashCode();
    if (m.strings != null)   for(String str : m.strings)        chksum ^= str.hashCode();
    if (m.ints != null)      for(Integer i : m.ints)            chksum ^= i.hashCode();
    return chksum;
  }

  /**
   * Message "factory" to add checksum and direction to our messages
   */
  private Message createMessage(Message o)
  {
    Message m = new Message();
    m.strings = o.strings;
    m.ints = o.ints;

    // add our current location to the front
    MapLocation[] newLocations = new MapLocation[(o.locations == null)? 1 : o.locations.length + 1];
    int locIdx = 0;
    newLocations[locIdx] = currLoc;
    if (o.locations != null) for (MapLocation loc : o.locations) newLocations[++locIdx] = loc;

    // scramble locations
    newLocations = scrambleLocations(newLocations);

    m.locations = newLocations;

    // add our checksum to the front
    int[] newInts = new int[(o.ints == null)? 1 : o.ints.length + 1];
    locIdx = 0;
    newInts[locIdx] = checkSum(m);
    if (o.ints != null) for (Integer i : o.ints) newInts[++locIdx] = i;

    m.ints = newInts;

    return m;
  }

  // Unwrap our "frame"s
  private Message unCreateMessage(Message m)
  {
    // This should never be called before checking if isLegitMessage()

    Message fm = new Message();
    fm.strings = m.strings;

    // remove the checksum from the message
    if (m.ints.length >= 2)
    {
      int[] newInts = new int[m.ints.length - 1];
      for (int idx = 0; idx < newInts.length; idx++)
        newInts[idx] = m.ints[idx + 1];
      fm.ints = newInts;
    }

    // remove the sender location from the message
    if (m.locations.length >= 2)
    {
      MapLocation[] newLocs = new MapLocation[m.locations.length - 1];
      for (int idx = 0; idx < newLocs.length; idx++)
        newLocs[idx] = m.locations[idx + 1];
      fm.locations = newLocs;
    }

    return fm;
  }

  /**
   * checks whether the message is legitimate from us
   */
  private boolean isLegitMessage(Message m)
  {
    // remove the checksum from the message

    Message fm = new Message();
    fm.locations = m.locations;
    fm.strings = m.strings;

    if (m.ints == null) return false;
    if (m.ints.length < 1) return false;

    int msgSum = m.ints[0];

    if (m.ints.length >= 2)
    {
      int[] newInts = new int[m.ints.length - 1];
      for (int idx = 0; idx < newInts.length; idx++)
        newInts[idx] = m.ints[idx + 1];
      fm.ints = newInts;
    }

    return checkSum(fm) == msgSum;
  }

  // Offensive strategy -- cause havoc to them, *maybe*?
  private void mutateMessageAttack(Message enemyMessage)
  { //modifies enemyMessage inplace
    Message copyEnemyMessage = (Message)enemyMessage.clone();
    if (copyEnemyMessage.ints != null)
    {
      for (int i = copyEnemyMessage.ints.length - 1; i > 0; i--)
      {
        copyEnemyMessage.ints[i] = copyEnemyMessage.ints[i] | copyEnemyMessage.ints[i-1]; //bitwise or
      }
      copyEnemyMessage.ints[0] = -1;
      /* for now, this number will be used so our robots can
       * recognize a message to ignore since the sum of maplocation x-coords and y-coords can't
       * be negative
       */
    }
    if (copyEnemyMessage.locations.length >= 2)
    {
      copyEnemyMessage.locations[1] = new MapLocation(Integer.MAX_VALUE, Integer.MAX_VALUE);
      copyEnemyMessage.locations[0] = null;
    }
    if (copyEnemyMessage.strings.length >= 2)
    { //switch elements 0 and 1
      String temp = copyEnemyMessage.strings[0];
      copyEnemyMessage.strings[0] = copyEnemyMessage.strings[1];
      copyEnemyMessage.strings[1] = temp;
    }
    safeBroadcast(copyEnemyMessage);
  }

  private void sendElection() // msg type 0
  {
    int[] ints = new int[]{ 0, // message type "elect"
      myID  // robot id
    };
    MapLocation[] locs = new MapLocation[]{
      currLoc
    };
    voterMandate = locs[0];

    Message m = new Message();
    m.ints = ints;
    m.locations = locs;

    ourBroadcast(m);
  }

  private void sendDataRequest() // msg type 2
  {
    int[] ints = new int[]{ 2 }; // message type "girl inform me"
    Message m = new Message();
    m.ints = ints;

    ourBroadcast(m);
  }

  private void sendAllData() // msg type 3
  {
    // This will be a pain in the ass to implement.
    // Do we really want it?
      /*
       * we should implement it if there's a need for robots to have more map data to make decisions. i'll do this 
       * sometime if no one else does this method. -kevin
       */
  }

  private void sendOrigin() // msg type 4
  {
    // don't broadcast if we're as dumb as them
    if (origin == null) return;
    // don't broadcast if we have recently
    if (originCoolDown != 0) return;

    int[] ints = new int[]{ 4 }; // message type "origin"
    MapLocation[] locs = new MapLocation[]{ origin };

    Message m = new Message();
    m.ints = ints;
    m.locations = locs;

    ourBroadcast(m);

    originCoolDown = 5;
  }

  private void sendTowerLocation(MapLocation loc) // msg type 5
  {
    int[] ints = new int[]{ 5 }; // message type "loc ness"
    MapLocation[] locs = new MapLocation[]{ loc };
    Message m = new Message();
    m.locations = locs;
    m.ints = ints;

    ourBroadcast(m);
  }

  MapLocation nextDest = null;
  private void processMessages() // deal with incoming messages
  {
    Message im;
    if ((im = outMessageQ.poll()) != null) safeBroadcast(im);

    while ((im = myRC.getNextMessage()) != null)
    {
      if (isLegitMessage(im))
      {
        Message m = unCreateMessage(im);
        switch (m.ints[0])
        {
          case 0: // election
            if (incumbentID > m.ints[1])
            {
              origin = m.locations[0];
              incumbentID = m.ints[1];
            }
            if (incumbentID > myID)
            {
              origin = voterMandate;
              incumbentID = myID;
            }
            break;
          case 2: // information request
            //sendAllData();
            sendOrigin();
            break;
          case 4: // origin broadcast
            if (origin == null) origin = m.locations[0];
            if (originCoolDown < 3) originCoolDown = 3;
            break;
          case 5: // tower location
            MapLocation tower = m.locations[0];
            nextDest = tower;
            Integer i = towers.get(tower);
            if (i == null)
            {
              towers.put(tower, 0);
              sendTowerLocation(tower);
            }
            break;
          default: // message we don't handle yet or are obsolete
            break;
        }
      }
      else
        interceptedEnemyMessages.add(im);
    }
  }

  private boolean reproduce() {
    if (myRC.getEnergonLevel() < MIN_SPAWN_ENERGON) return false;
    if (myRC.hasActionSet()) myRC.yield();
    Direction currDir = myRC.getDirection();            
    MapLocation inFront = currLoc.add(currDir); 
    try {
        if (map.get(inFront) == null && myRC.senseGroundRobotAtLocation(inFront) == null) 
        //if (map.get(inFront) == null && myRC.senseAirRobotAtLocation(inFront) == null)
        {
            myRC.spawn(RobotType.SOLDIER);            
            myRC.yield();
            Robot temp = myRC.senseGroundRobotAtLocation(inFront);
            if (temp != null) fillUp(temp, inFront, myRC.getEnergonLevel(), RobotLevel.ON_GROUND);
            return true;
        } else {
            while (myRC.isMovementActive()) myRC.yield();
            myRC.setDirection(currDir.rotateLeft());
            myRC.yield();                
        }
    } catch (GameActionException ex) {
        ex.printStackTrace();
    }
    return false;
  }
}